
#include <stdio.h>
#include <stdlib.h>

#include "algos.h"
#include "typ.h"

#include "libcoord.h"
#include "libgraphe.h"
#include "libtas.h"
#include "string.h"


// Affiche le contenu d'un tableau d'entiers
void afficheTab(int* cheminRes, int nbSommets){
	int i;

	printf("chemin : -");
		for(i=0;i<nbSommets;i++)
			printf("%d-",cheminRes[i]);
		printf("\n");
}

/*
 * Fonction :		calculeLongueurParcours
 *
 * Parametres :		int* chaine 		le tableau constituant un parcours 
 *					int size			la taille du tableau "chaine"
 *					TypGraphe* g		le graphe
 *
 * Retour :			longueur totale du cycle
 *
 * Description :	Calcule la somme des longueurs entre chaque sommet,
 *					en n'omettant pas la longueur entre le 1er et le dernier sommet.  
 *
 */
double calculeLongueurParcours(int* chaine, int size, TypGraphe* g){
	int i;
	double sumP; 
	
	sumP = getPoidsArete(g, chaine[size-1],chaine[0]);
	
	for(i=0;i<size-1;i++)
		sumP += getPoidsArete(g, chaine[i],chaine[i+1]);	

	return sumP;
}


/*
 * Fonction :		enumereCycles
 *
 * Parametres :		int* prefixe 		le tableau constituant le début d'un parcours 
 *					int sizePrefixe		la taille du tableau "prefixe"
 *					int* V				l'ensemble des sommets du graphe
 *					int nbSommets		le nombre de sommets du graphe 
 *					TypGraphe* g		le graphe 
 *					int** tabRes		le tableau correspondant au meilleur parcours
 *					double* doubleRes	le poids du chemin contenu dans "tabRes"
 *
 * Retour :			rien (mais le tableau tabRes est passé par adresse, 
					ce qui permet de récupérer le meilleur parcours )
 *
 * Description :	enumération recursive de tout les chemins possibles du graphe,
 * 					calcul simultané du poids de chaque chemin, et sauvegarde du meilleur.  
 *				
 */
void enumereCycles(int* prefixe, int sizePrefixe, int* V, int nbSommets, TypGraphe* g ,int* tabRes, double* doubleRes){
	
	int i,j;
	int taille;		//	taille du tableau V

	int* parcours;	//	chemin temporaire
	double tmp_res;	//	poids minimal temporaire
	
	int* Vcopy;		// une copie de V avec un sommet en moins

	taille = nbSommets - sizePrefixe;
	
	// S'il ne reste plus qu'un sommet à ajouter pour compléter un chemin
	if (taille == 1){
		// on crée le chemin en combinant le prefixe et le sommet restant dans V
		parcours = (int*)malloc(sizeof(int)*(nbSommets));

		for ( j = 0 ; j < nbSommets - 1 ; j++ )
     		parcours[j] = prefixe[j];
 		parcours[j] = V[0];

		
 		tmp_res = calculeLongueurParcours(parcours,nbSommets,g);

		/*DEBUG*/
		// printf(" parcours = %f",tmp_res);
		// afficheTab(parcours,nbSommets);
		
		//	Soit aucun chemin n'a encore été calculé, on enregistre ce 1er parcours,
		//	Soit on compare ce chemin avec le meilleur trouvé jusqu'ici, 
		//	et on le remplace par ce nouveau parcours si celui-ci est meilleur
		
		if (*doubleRes == 0 || tmp_res < *doubleRes){
			*doubleRes = tmp_res;
			for ( j = 0 ; j < nbSommets ; j++ )
				tabRes[j] = parcours[j];
		}	
		free(parcours);
	
	}else{

		//	Sinon on continue d'énumérer

		for(i=0;i<taille;i++){

			prefixe[sizePrefixe] = V[i];
			Vcopy = (int*)malloc(sizeof(int)*(taille-1));
			for ( j = 0 ; j < i ; j++ )
				Vcopy[j] = V[j];
			for ( j = i ; j < taille - 1 ; j++ )
         		Vcopy[j] = V[j+1];
         	
			enumereCycles(prefixe,sizePrefixe+1,Vcopy,nbSommets,g,tabRes,doubleRes);
			free(Vcopy);
		}
	}
}


/*
 * Fonction :		plusProcheVoisin
 *
 * Parametres :		TypGraphe* g		le graphe 
 *					int nbSommets		le nombre de sommets du graphe 
 *					int** cheminRes		le tableau correspondant au meilleur parcours
 *
 * Retour :			le poids du meilleur chemin (et le tableau cheminRes qui est passé
 *					par adresse, ce qui permet de récupérer le meilleur parcours )
 *
 * Description :	création d'un chemin en partant d'un sommet (ici le 1) et en ajoutant
 * 					systématiquement le plus proche sommet du dernier sommet inséré.
 *				
 */
double plusProcheVoisin(TypGraphe* graphe, int nbSommets, int* cheminRes){

	int i,j;
	
	int* cheminColor;	//	tableau permettant de savoir si un sommet a déjà été ajouté au chemin 

	int tailleChem;		//	taille du chemin en création

	int minSommet;		//	le plus proche sommet
	double minPoids;	// le poids entre le dernier sommet ajouté et minSommet;    


	cheminColor = (int*) calloc(sizeof(int),nbSommets+1);
	
	// initialisation du chemin avec 1 sommet : 1
	cheminRes[0] = 1;
	tailleChem = 1;
	
	// Coloriage du sommet déjà ajouté au chemin
	cheminColor[1] = 1;

	minSommet = -1;
	minPoids = -1.;	

	//	Tant que tout les sommets n'ont pas été ajouté au chemin,
	while( nbSommets > tailleChem ){
		
		//	on récupère le dernier sommet ajouté dans la chaîne,
		i = cheminRes[tailleChem-1] ;

		//	on cherche son plus proche sommet ...
		for(j=1;j<nbSommets+1;j++){
			//	... qui n'a pas encore été ajouté au chemin. 
			if( cheminColor[j] == 0){
				
				//	On initialise les "min" la 1ère fois... 
				//	ou on les remplace avec le potentiel meilleur sommet et poids d'arête trouvés
				if (minSommet == -1 || minPoids > getPoidsArete(graphe,i,j)){
					minPoids = getPoidsArete(graphe,i,j);
					minSommet = j;
				}
			}
		}

		// on ajoute le sommet trouvé à notre chemin
		cheminRes[tailleChem] = minSommet;
		cheminColor[minSommet] = 1;

		/*DEBUG*/
		//	afficheTab( cheminRes, tailleChem );
		
		tailleChem++;

		minSommet = -1; 
		minPoids = -1;
	}
	free(cheminColor);
	return calculeLongueurParcours(cheminRes, nbSommets, graphe);

}

double plusPetitDetour(TypGraphe* graphe, int nbSommets, int* cheminRes){

	int tailleChem;		//	taille du chemin en création;
	
	int* cheminColor;	//	tableau permettant de savoir si un sommet a déjà été ajouté au chemin 
	
	int shc; 			//	sommet hors chemin	
	int sdc1,sdc2; 		//	sommets consécutifs dans le chemin
	
	TypArete *besta; 	//	récupère le plus petit des plus petits détours de chaque sommet 
	TypArete *tmp_a; 	// récupère le plus petit détour d'un sommet donné
	
	/*	
		TypArete*->v1 sert à stocker le sommet à insérer 
		TypArete*->v2 sert à stocker l'indice dans lequel il faut insérer le sommet 
	*/

	int best_shc;		//	le sommet à insérer 
	int indiceInser; 	//	l'indice dans lequel il faut insérer le sommet

	double detour_tmp ;

	int i,j;
	int sommetChoisi = 1;

	besta = (TypArete*) malloc(sizeof(TypArete));
	tmp_a = (TypArete*) malloc(sizeof(TypArete));

	// initialisation
	tmp_a->poids = -1;
	besta->poids = -1;
	
	// on choisit un sommet (ici 1)
	cheminRes[0] = 1;

	tailleChem = 1;

	cheminColor = (int*) calloc(sizeof(int),nbSommets+1);

	// Coloriage du (ou des) sommet(s) déjà ajouté(s) au chemin
	cheminColor[sommetChoisi] = 1;


	//	Tant que tout les sommets n'ont pas été ajouté au chemin,
	while( nbSommets > tailleChem ){
		
		afficheTab( cheminRes, tailleChem );
		printf(" -- %f\n", calculeLongueurParcours(cheminRes, tailleChem, graphe));
		
		// Pour chaque sommet non présent dans cheminRes
		for(shc=1;shc<nbSommets+1;shc++){
			
			if(cheminColor[shc] == 0){
				// calculer pour tout sommet consécutif de cheminRes la valeur du détour,
				// et stocker la plus petite
				tmp_a->v1 = shc;
				for(i=0 ; i<tailleChem ; i++ ){

					sdc1 = cheminRes[i];
					
					j = (i+1)%tailleChem;
					sdc2 = cheminRes[j];

					// calcul du détour
					detour_tmp = getPoidsArete(graphe,shc,sdc1) + getPoidsArete(graphe,shc,sdc2) - getPoidsArete(graphe,sdc1,sdc2);

					//	On initialise les "min" la 1ère fois...
					//	ou on les remplace avec le potentiel meilleur sommet et poids d'arête trouvés
					if(tmp_a->poids == -1 || tmp_a->poids > detour_tmp ){
						tmp_a->poids = detour_tmp;
						tmp_a->v2 = i<j ? j : i ;
					}
				}

				// Stocker les infos du plus petit des plus petits détours trouvés 
				
				//	On initialise les "min" la 1ère fois...
				//	ou on les remplace avec le potentiel meilleur sommet et poids d'arête trouvés

				if( besta->poids == -1 || besta->poids > tmp_a->poids ){
					besta->poids = tmp_a->poids;
					besta->v1 = tmp_a->v1;
					besta->v2 = tmp_a->v2;
				}

				// on réinitialise 
				tmp_a->poids = -1;
			}
		}
		
		// on récupére le plus petit des détours
		best_shc = besta->v1;
		indiceInser = besta->v2;
		
		// et on l'ajoute à cheminRes :

		// on décale les valeurs situées après indiceInser
		for(i=tailleChem;i<indiceInser;i--)
			cheminRes[i] = cheminRes[i-1];

		// on ajoute le nouveau sommet 
		cheminRes[i] = best_shc;

		tailleChem++;
		cheminColor[best_shc] = 1;

		// on réinitialise 
		besta->poids = -1;
		
	}

	free(cheminColor);
	free(besta);
	free(tmp_a);

	return calculeLongueurParcours(cheminRes, nbSommets, graphe);

}



double parcours_arpm(TypGraphe* graphe, int nbSommets, int* cheminRes) {
	
	cheminRes[0] = 1;
	int i;
	int cheminColor[nbSommets+1];
	for(i=0;i<nbSommets+1;i++)
		cheminColor[i] = 0;

	TypGraphe* gArpm = arpm(graphe);
	printf("* ARPM associé au graphe traité *\n");
	sortieGraphe(NULL, gArpm);
	int sizeChemin = 1;
	int sommet = 1;
	
	parcours_arpm_rec(gArpm, nbSommets, &sommet, cheminColor, cheminRes, &sizeChemin);
	supprimerGraphe(&gArpm);

	return calculeLongueurParcours(cheminRes, nbSommets, graphe);
}

// Parcourt un ARMP en profondeur avec un graphe complet
void parcours_arpm_rec(TypGraphe* graphe, int nbSommets,  int* sommet, int* cheminColor, int* cheminRes, int* sizeChemin) {
	
	cheminColor[*sommet] = 1;
	// printf("Chemin - Color ");afficheTab(cheminColor,nbSommets+1);
	// printf("Chemin Resultat ");afficheTab(cheminRes,*sizeChemin);
	//printf("sommet : %d\n",*sommet);
	
	TypVoisins* tv = (graphe->listesAdjacences[*sommet])->voisinSuivant;

	while (tv->voisin != -1){
		
		printf("sommet du parcours : %d\n",tv->voisin);
		if(tv->voisin != -1 && cheminColor[tv->voisin] != 1){
			cheminRes[*sizeChemin] = tv->voisin;
			*sommet = tv->voisin;
			*sizeChemin = *sizeChemin + 1; 
			parcours_arpm_rec(graphe, nbSommets, sommet, cheminColor,cheminRes,sizeChemin);
		}
		tv = tv->voisinSuivant;
	}
}




// Applique l'algorithme de Christofides à un graphe complet
void christofides(TypGraphe* graphe, int nbSommets, int* cheminRes, double* distRes) {

	TypGraphe* arbre = arpm(graphe);
	printf("* ARPM associé au graphe traité *\n");

	sortieGraphe(NULL, arbre);
	appairerSommets(arbre, nbSommets);
	supprimerGraphe(&arbre);

}

void appairerSommets(TypGraphe* graphe, int nbSommets){
	int i,cpt,nbSomImpairs;
	int* tabImpairs = (int*)calloc(sizeof(int),nbSommets);
	cpt = 0;
	nbSomImpairs = 0;
	for(i=1;i<nbSommets+1;i++){
		cpt = 0;
		if(graphe->listesAdjacences[i] != NULL){
			TypVoisins* tv = (graphe->listesAdjacences[i])->voisinSuivant;
			while (tv->voisin != -1){
				cpt++;
				tv = tv->voisinSuivant;
			}
		}
		if( cpt %2 == 1){
			tabImpairs[nbSomImpairs] = i;
			nbSomImpairs++;
		}
	}

	printf("tabImpairs ");afficheTab(tabImpairs,nbSomImpairs);

}
